package hard;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

public class Hua17_2 {
    private static int taskScheduler(int resourcesNum, int[][] taskAttributes) {
        class Task {
            public final long start;
            public final int time;
            public final int priority;

            public Task(int time, int priority) {
                this(time, priority, -1);
            }

            public Task(Task task, long start) {
                this(task.time, task.priority, start);
            }

            private Task(int time, int priority, long start) {
                this.time = time;
                this.priority = priority;
                this.start = start;
            }
        }

        List<Task> tasks = new ArrayList<>();
        for (int[] taskAttribute : taskAttributes) {
            tasks.add(new Task(taskAttribute[0], taskAttribute[1]));
        }
        tasks.sort((o1, o2) -> {
            if (o1.priority != o2.priority) {
                return o1.priority - o2.priority;
            }
            return o2.time - o1.time;
        });

        PriorityQueue<Task> VMs = new PriorityQueue<>(Comparator.comparingLong(o -> o.start + o.time));
        long time = 0;

        for (Task task : tasks) {
            if (VMs.size() >= resourcesNum && !VMs.isEmpty()) {
                time += VMs.peek().start + VMs.peek().time - time;
                while (!VMs.isEmpty() && VMs.peek().start + VMs.peek().time <= time) {
                    VMs.poll();
                }
            }
            VMs.add(new Task(task, time));
        }

        int leftMax = Integer.MIN_VALUE;
        for (Task task : VMs) {
            leftMax = (int) Math.max(leftMax, task.start + task.time - time);
        }

        return (int) ((time + leftMax) % (1e9 + 7));
    }
}
